package LearnDataStructure.d_图结构.f_最短路径by单元;

import java.util.HashSet;
import java.util.Set;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-15 18:57
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.d_图结构.f_最短路径by单元
 */
/*
Dijkstra算法采用的是一种贪心的策略，
声明一个数组dis来保存源点到各个顶点的最短距离
和一个保存已经找到了最短路径的顶点的集合：T，

初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。
若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,
同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。

初始时，集合T只有顶点s。

然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，
并且把该点加入到T中，OK，此时完成一个顶点，
然后，我们需要看看新加入的顶点是否可以到达其他顶点
并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，
如果是，那么就替换这些顶点在dis中的值。
然后，又从dis中找出最小值，
重复上述动作，直到T中包含了图的所有顶点。
 */
public class g_Dijkstra动规 {
    public static void main(String[] args) {
        g_Dijkstra动规 test = new g_Dijkstra动规();
        test.useDijkstra();
    }

    public void useDijkstra() {
        int[][] graph = {
               //a  b  c  d  e  f  g
                {0, 2, 5, 0, 0, 0, 0},  //a
                {2, 0, 4, 6, 10, 0, 0}, //b
                {5, 4, 0, 2, 0, 0, 0},  //c
                {0, 6, 2, 0, 0, 1, 0},  //d
                {0, 10, 0, 0, 0, 3, 5}, //e
                {0, 0, 0, 1, 3, 0, 9},  //f
                {0, 0, 0, 0, 5, 9, 0}   //g
        };

        int[] parent = new int[graph.length];

        int[] result = Dijkstra(1, graph, parent);//以b作为start

        for (int i = 0; i < parent.length; i++) {
            System.out.println((char) ('A' + 1) + "到" + (char) ('A' + i) + "的路径");
            System.out.print((char) ('A' + i) + "<-");
            int j = parent[i];
            while (j != 1) {
                System.out.print((char) ('A' + j) + "<-");
                j = parent[j];
            }
            System.out.print((char) ('A' + j));
            System.out.println(":" + result[i]);
        }
    }

    /**
     * 从start开始，遍历各个节点，寻找最短路径
     * @param start
     * @param graph
     * @param parent
     * @return
     */
    public static int[] Dijkstra(int start, int[][] graph, int[] parent) {
        //节点个数
        int N = graph.length;
        //初始化，源点的前驱是自身
        parent[start] = start;
        //初始化，记录start到各顶点的最短距离;start到start的距离为0
        int[] result = new int[N];
        result[start] = 0;
        //初始化，记录已经找到最短距离的顶点,使用hashSet方便查询;首先标记start
        HashSet<Integer> visited = new HashSet<>();
        visited.add(start);

        /*
        第一步：初始化直接可达的顶点，
        用直连的权值来初始化result[i],即可直达的把距离记录下来作为待定值
         */
        for (int i = 0; i < N; i++) {
            if (i != start && graph[start][i] == 0) {//当前的节点i与start没有边相连
                result[i] = Integer.MAX_VALUE;
            }
            if (i != start && graph[start][i] > 0) {//有边；先暂时把直连的权值作为result[]结果；同时标记i节点的前驱parent[i]为start
                result[i] = graph[start][i];
                parent[i] = start;
            }
        }

        while (visited.size() < N) {
            /*
            第二步：试探
            从未被标记的点中
            找到“最小的权值的边”的点，
            这个“最小的权值”可以作为确定值放入到result[]中
             */
            int minValueNode = findMinPath(result,visited);
            visited.add(minValueNode);//添加标记
            if (visited.size() == N) {//如果添加标记操作后，完成了所有点都被标记了，那么寻找完毕，直接退出
                break;
            }
            /*
            第三步：验证
            看看从start出发,
            到底是“经过”这个minValueNode到其邻居近（start -> minValueNode -> neighbor）
            还是“直达”更近,（start -> neighbor）
            如果“经过”更近就要更新
             */
            for (int neighbor = 0; neighbor < N; neighbor++) {//因为不清楚minValueNode有多少邻居，所以需要穷举
                int distance = graph[minValueNode][neighbor];//distance可能为0，即不存在边
                if (distance > 0 && result[neighbor] > result[minValueNode] + distance) {//如果存在边，同时“经过”比“直达”要近
                    //就需要下面两行的更新
                    result[neighbor] = result[minValueNode] + distance;
                    parent[neighbor] = minValueNode;
                }
            }
        }
        return result;
    }

    /**
     * 从未被标记visited的点中
     * 寻找权值最小的点
     * 这些点虽然没有被标记，但是可能存在对应的result[]
     * 当然大部分点仍然是Integer.MAX_VALUE状态
     * @param result
     * @param visited
     * @return
     */
    public static int findMinPath(int[] result, Set<Integer>visited) {
        int minValueNode = -1;
        int minValue = Integer.MAX_VALUE;
        for (int i = 0; i < result.length; i++) {
            if (!visited.contains(i) && result[i] < minValue) {
                minValue = result[i];
                minValueNode = i;
            }
        }
        //跳出循环后，minValueNode作为“最小的权值的边的节点”，这个“最小的权值”可以作为确定值放入到result[]中
        return minValueNode;
    }
}
